package com.zk.algorithm.sort;

import com.zk.algorithm.Utils;

/**
 * 归并排序
 *
 * @author zk
 */
public class MergeSort {

    public static void main(String[] args) {
        //Initializing array
        int arr[] = {9, 4, 8, 3, 1, 2, 5};
        mergesort(arr, 0, arr.length - 1);

        Utils.println(arr);
    }

    //Sorting in non decreasing order
    private static void mergesort(int[] arr, int i, int j) {
        if (i < j) {
            int mid = (i + j) / 2;
            //System.out.println("mid="+mid);
            mergesort(arr, i, mid);
            mergesort(arr, mid + 1, j);
            merge(arr, i, mid, j);
        }
    }

    private static void merge(int[] arr, int i, int mid, int j) {
        // 辅助数组
        int temp[] = new int[arr.length];

        int l = i;
        int r = j;
        int m = mid + 1;
        int k = l;

        while (l <= mid && m <= r) {
            if (arr[l] <= arr[m]) {
                temp[k++] = arr[l++];
            } else {
                temp[k++] = arr[m++];
            }
        }

        while (l <= mid)
            temp[k++] = arr[l++];

        while (m <= r) {
            temp[k++] = arr[m++];
        }

        // 辅助数组中的值拷贝到原 array
        for (int i1 = i; i1 <= j; i1++) {
            arr[i1] = temp[i1];
        }
    }

}
